#include <bits/stdc++.h>

using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
		vector<vector<int>> res;
		if (!root) return res;

		vector<int> layer; TreeNode* last = root;
		queue<TreeNode*> aux { { root } };
		while (!aux.empty()) {
			auto ptr = aux.front(); aux.pop();
			layer.emplace_back(ptr->val);

			if (ptr->left) aux.emplace(ptr->left);
			if (ptr->right) aux.emplace(ptr->right);

			if (ptr == last) {
				res.emplace_back(move(layer));
				layer.clear();
				last = aux.back();
			}
		}

		reverse(res.begin(), res.end());
		return res;
	}
private:
};

int main()
{
	Solution solution;
	return 0;
}
